FIG. 1 depicts an asynchronous transfer mode (ATM) communications network 10. The invention is illustrated herein for a broadband integrated service digital network 10 (B-ISDN) although the invention is equally applicable to other kinds of ATM capable communications networks 10 such as synchronous optical networks (SONET). Furthermore, the model of a telephone network is used to illustrate the invention although the invention is also applicable to cable television networks, computer data networks, etc. The communications network 10 has plural nodes n1, n2, n3, n4, n5, n6, n7, n8, n9, n10, n11 and n12 which are interconnected by communication links. The communication links may include unshielded twisted pairs of wires, coaxial cables, optical fibers, satellite transponders, switches, etc. In the communications network 10, the nodes n1, n2, n3, n4, n5 and n6 are terminal equipments or TE's. For example, the TE's are customer premises equipments or CPE's such as telephones, set top boxes, cable television head ends or host computers. The nodes n7 and n8 are network termination units or NT's. The nodes n9, n10, n11 and n12 are, for example, central office switches which include ATM switches.
Communication is achieved in the communication network 10 by transmitting bitstreams on the links. Each bitstream is organized into fixed length time slots. Each node that desires to communicate writes fixed length packets called "cells" into the timeslots. FIG. 2 depicts an illustrative cell 20. The cell 20 has a header portion 22 into which the node writes overhead control information and a payload portion 24 into which the node writes a message to be conveyed. The node which desires to transmit a cell writes the cell thus generated into a particular time slot of the bitstream transmitted on a selected outgoing link.
According to ATM, communication is achieved by transmitting cells that contain messages along a sequence of nodes of the communications network 10. Specifically, the cells are transmitted via a sequence of individual connections between pairs of nodes of the communications network. See M. DE PRYKER, ASYNCHRONOUS TRANSFER MODE SOLUTION FOR BROADBAND ISDN, 2d ed., ch. 2.4.5.4, p. 84-87 (1995). This sequence of connections is illustratively predefined during a set up procedure when the communication is initiated. For example, to enable communication between the node n1 and the node n4, the following sequence of connections between nodes may be set up from the node n1 to the node n4 as follows:
node n1.fwdarw.node n7.fwdarw.node n9.fwdarw.node n10.fwdarw.node n11.fwdarw.node n8.fwdarw.node n4 PA1 node n4.fwdarw.node n8.fwdarw.node n11.fwdarw.node n12.fwdarw.node n10.fwdarw.node n9.fwdarw.node n7.fwdarw.node n1. PA1 (a) using a predetermined scheduling policy and a predetermined quality of service for communications, determining a maximum equivalent aggregate average power .PSI..sub.max of the arrival rate of cells for all calls admitted to a node, which still maintains the predetermined QoS, as a function of an aggregate power spectrum DC component .gamma..sub.T and a constant equivalent half-power bandwidth B.sub.e of the arrival rate of cell for all calls, for which B.sub.e individual component equivalent average powers .PSI..sub.e are determined for all calls, PA1 (b) storing the value of .PSI..sub.max determined in step (a) in a table entry that is indexed by the value of .gamma..sub.T used to determined the stored value of .PSI..sub.max, and PA1 (c) repeating steps (a)-(b) for multiple different values of .gamma..sub.T in a range of expected values for .gamma..sub.T. PA1 (a) producing power spectrum DC component .gamma., half power bandwidth B.sub.w, and average power .PSI..sub.w parameters of a cell arrival rate of a new call, PA1 (b) transforming the parameters .gamma., B.sub.w, .PSI..sub.w to .gamma., an equivalent half power bandwidth B.sub.e, and an equivalent average power .PSI..sub.e, wherein B.sub.e is a predetermined constant, PA1 (c) retrieving from a predetermined table, a maximum aggregate equivalent average power .PSI..sub.max that can be accommodated by the node for all admitted calls which is indexed by the sum of an aggregate power spectrum DC component .gamma..sub.T for all calls currently admitted at the node and .gamma., and PA1 (d) determining whether or not to admit the call by comparing a sum of an aggregate average power .PSI..sub.T of all calls currently admitted and .PSI..sub.e to .PSI..sub.max.
Likewise, a return sequence of connections between nodes may be set up from the node n4 to the node n1 as follows:
The node n1 or n4 which generates cells for transmission is referred to as a source node. The node n4 or n1 which is the ultimate intended recipient of the cells is referred to as the destination node. Each other node n7, n9, n10, n11, n8 or n12 is an intermediate node.
A virtual channel (VC) is defined as a communication channel dynamically allocated by a node for transmitting cells of a particular connection to a second device. The collection of all VC's of a sequence of connections is referred to as a virtual channel connection (VCC). In setting up a sequence of connections, a VCC identifier is assigned to the communication. Each node (e.g., the node n8) in the sequence of nodes (e.g., n1, n7, n9, n10, n11, n8, n4) allocates a virtual channel for conveying cells to the next node in the sequence of nodes for the communication (e.g., the node n4). Each node of the sequence of nodes creates an entry in a routing table for each communication. Each entry is indexed by the VCC identifier of the respective communication and contains information regarding how to transmit received (or newly generated) cells to the next node of the sequence of nodes. For instance, the indexed routing table entry may contain an indication of the virtual channel for routing the cell, such as a virtual channel identifier (VCI).
Once the sequence of connections is set up, the source node (e.g., n1) generates one or more cells 20. The source node n1 writes the VCC identifier assigned to the communication in the cell header 22 and messages to be conveyed to the destination node (e.g., n4) in the cell payload 24. The node n1 then writes the generated cells 20 into particular timeslots of an outgoing bitstream transmitted to the next node (e.g., node n7) of the sequence of nodes for that communication. Each intermediate node (e.g., the node n7) which receives the cell 20, utilizes the VCC identifier stored in the cell to access a routing table thereat. The intermediate node (e.g., the node n7) utilizes the retrieved routing table entry (specifically, the VCI of the retrieved routing table entry) to transmit the cell on the appropriate VC to the next node (e.g., node n9) of the sequence of nodes. This process is repeated at each intermediate node (e.g., n9, n10, n11 and n8) until the cell arrives at the destination node n4.
Note also that the ATM protocol permits two nodes to set up semi-permanent connections for conveying multiple simultaneous VCC's between the nodes. Such semi-permanent connections are referred to as virtual paths (VP's). VP's are illustratively also designated in each cell header by a respective virtual path identifier (VPI).
In transmitting cells on VC's, each node writes a cell into a time slot of an outgoing bitstream destined to another node, which time slot is allocated for the VC. Likewise, each node selectively reads cells from timeslots of received incoming bitstreams and performs the same writing operation to other outgoing bitstreams. This form of adding and dropping of cells from different bitstreams is referred to cell layer multiplexing. (Cell layer multiplexing should be distinguished from physical layer multiplexing wherein multiple lower rate bitstreams are simply combined into a higher rate bitstream or a higher rate bitstream is divided into multiple lower rate bitstreams.)
According to ATM, the number of timeslots of specific outgoing bitstreams allocated to carrying cells of each VC varies over time depending on the instantaneous traffic load at that moment at the node. Illustratively, the bandwidth, i.e., bit rate, of each outgoing bitstream is a finite amount, such as 155 Mbits/sec (but need not be the same at each outgoing link of a node). In the event that too much traffic, i.e., too many cells are to be transmitted in an outgoing bitstream, than can be accommodated at that moment, congestion is said to occur. In the event of congestion at a node, the node may discard excess cells. Discarded cells may be retransmitted from the source node upon determining that the cells were discarded. Since congestion tends to be a spontaneous and short duration event, the discarding of cells tends to reduce the traffic load (number of cells to be transmitted in a given bitstream at one time) and alleviate the congestion. Consider that some source nodes produce cells at a constant rate while other produce cells at a variable rate which exhibits a mean bit rate and a peak bit rate. Furthermore, the arrival of cells from each source node is somewhat randomly distributed over time. Therefore, congestion is alleviated in spite of the fact that discarded cells are retransmitted from the source node.
When cells are discarded, a delay is introduced in the delivery of those cells. This poses a problem in the communication system 10. Consider that cells may contain messages for different types of communications. In some communications, the cells may contain general transactional data. Such cells are generally not time sensitive; a delay in transmitting cells does not degrade the communication. On the other hand, in other communications, the cells may contain video, audio or interactive communication information. Such cells are very time sensitive. Delayed video or audio data bearing cells can cause audio and video decoders to underflow, resulting in psycho-audially or psycho-visually perceptible discontinuities in the audio or video. Such discontinuities are at best annoying and at worst render the audio or video unintelligible. Delays in interactive data bearing cells can produce echoes if there is a cross-coupling between both directions of the communication. Alternatively, the delays may require that the participants on each end of the communication wait perceptibly long periods before receiving a response to their messages. This degrades the interactive communication since neither echoes nor perceptible delays occur in an ordinary interactive conversation.
Each communication may be associated with a quality of service or (QoS) requirement. QoS may be expressed in terms of different maximum communication tolerances such as cell transfer delay, delay jitter, cell loss ratio and/or burst cell losses. Generally speaking, interactive, audio and video data bearing cells have more strict QoS requirements than transactional computer data. Nodes may use the QoS of each communication as a basis for avoiding congestion. However, the occurrence of congestion and the prediction of traffic loads in general is a non-linear function.
The prior art has suggested several methods for controlling congestion and admission (described below) in an ATM communications network. See R. Guerin, H. Ahamadi & M. Nagahshineh, Equivalent Capacity and Its Application to Bandwidth Allocation in High-Speed Networks, IEEE J. SELECT. AREAS COMM., vol. 9, no. 7, pp. 968-981, September., 1991; S. Q.Li & S. Chong, Fundamental Limits of Input Rate Control in High Speed Network PROC. INFOCOM'93, pp. 662-671 (1993); A. Hiramatsu, ATM Communications Network Control by Neural Networks, IEEE TRANS. NEURAL NETWORKS, vol. 1, no. 1, pp. 122-130, March, 1990; T. D. Ndousse, Fuzzy Neural Control of Voice Cells in ATM Networks, IEEE J. SELECT. AREAS COMM., vol. 12, no. 9, pp. 1488-1494, December 1994; A. Bonde & S. Ghosh, A Comparative Study of Fuzzy Versus "Fixed" Thresholds for Robust Queue Management in Cell-Switching Networks, IEEE TRANS. NETWORKING, vol. 2, no. 4, pp. 337-344, August 1994; U.S. Pat. No. 5,341336; U.S. Pat. No. 5,179,556; and U.S. Pat. No. 5,442,624. The traffic control strategies can be categorized into two categories, namely, admission control and congestion control. The admission control strategies determine whether or not a particular node should establish a VC for a new communication based on whether or not the additional cells produced by the new communication are likely to cause congestion. The congestion control strategies adjust the production of cells for each communication for which a VC has already been established by a particular node in an attempt to reduce the traffic load at the node and thereby avert the occurrence of congestion.
The Guerin reference proposes an "equivalent capacity method" for determining whether or not to admit a new communication to (accommodate the communication by allocating a VC during set up at) a node. The node receives the mean bit rate, the peak bit rate, the peak bit rate duration and a QoS requirement for the new communication. Using these parameters, the node simulates a multimedia traffic source through a linear mathematical analysis in order to determine the bandwidth that the node must provide in order to accommodate the new communication. The disadvantage of this method is that the linear mathematical analysis is complicated requiring the use of approximations in order to perform the requisite calculations in real time. Furthermore, in order to guarantee the QoS requirement of the new communication, the node must overestimate the equivalent capacity needed by the new communication. Based on simulation analysis, this method results in a low utilization of system resources. That is, far too many communications are refused admission to each node resulting in under-utilization of the bandwidth of each outgoing bitstream at each node.
The Hiramatsu reference proposes to use a neural network to "learn" the relationship between the QoS which can be delivered by the network and the communication parameters observed at the node (e.g., cell arrival rate, cell loss rate, etc.) and specified by the new communication (e.g., average bit rate, bit rate fluctuation, etc.). Based on the learned relationship, a node can determine whether or not to admit a new communication. There are several problems with this technique. First, the number of neural nodes is closely related to the complexity of the decision function evaluated in determining the QoS to communication parameter relationship. Currently, there is no well-defined and comprehensive model which can be used as a frame of reference in designing the decision function. Second, the decision function that the neural network "learns" is relevant to only a particular kind of traffic. If there is any traffic change in the network, the neural network must be retrained to the new network conditions, possibly requiring the addition of neural nodes.
The Li reference proposes a two-threshold congestion control method. Each node which transmits cells to another node is presumed to operate according to a "leaky-bucket" mechanism. According to the leaky bucket mechanism, cells which are to be transmitted are stored in a queue. A token pool is provided with first and second types of tokens. If a token is available in the token pool and a cell is available for output at the head of the queue, the available cell is outputted from the queue and a token is deleted from the token pool. Tokens are replenished to the pool on a constant time basis. Initially, only tokens of the first type are used to output cells. When the first type of tokens are completely depleted, tokens of the second type are then used to transfer cells to the output queue. In the event too many cells are received than total tokens of the first and second type (and which can be buffered in the queue), the excess cells are discarded. In the event congestion occurs at the recipient node, then cells corresponding to tokens of the second type are discarded to avert congestion. The total number of cells of the first type correspond to a first threshold of cells which are not discarded in the event of congestion. The total number of cells of the second type correspond to a second threshold. The cells corresponding to the second type of tokens (produced beyond the first threshold, but below the second threshold) might be discarded in the event of congestion. Those cells produced beyond the second threshold are automatically discarded to avert congestion. The problem with this method is that it is difficult to acquire complete statistics on the occurrence of congestion in a communications network. Therefore, it is difficult to establish the two thresholds. Furthermore, the rationale for establishing the two thresholds is unclear.
U.S. Pat. No. 5,179,556 proposes a traffic control mechanism directed to prioritizing cells for selected transmission depending on whether or not the cells are part of a burst. A source of cells "encodes" the cells to indicate whether the cells are at the start, middle or end of a train of cells in a burst. Lone cells not part of a burst are not encoded. Each node has a state machine associated with each outgoing link. The state machine determines whether or not to block or transmit received cells. (The state machines can only have two states: block or transmit). The state machine decodes each encoded cell and uses the burst codes as a basis for permitting a transition from one state to another. That is, a state machine can transition from the blocking state to the transmit state, or vice versa, only at the beginning or end of a burst, not in the middle of a burst. This reference also proposes a connection admission mechanism which uses a single threshold to determine whether or not to admit a new communication to a node. The problem with this reference is that traffic loads are difficult to predict thus making it difficult to establish appropriate criterion (i.e., thresholds) for determining when to transition from a transmit state to a blocking state or when there is available capacity to support new communications at a node.
U.S. Pat. No. 5,341,366, the Bonde reference and the Ndousse reference propose to use fuzzy logic and fuzzy set theory in either congestion or admission control. Fuzzy logic and fuzzy sets can best be explained in comparison to ordinary logic and sets. In ordinary logic, each constant and logical predicate may have only one of two values, namely, true or false (or 0 or 1). In fuzzy logic, each constant and predicate may have a whole continuum of values between true and false or 0 or 1. These values represent a possibility between 0 and 1 that the corresponding fuzzy logic constant or predicate is true. Likewise, in ordinary set theory, a predicate function can be defined over a group of set elements which determines whether or not a set element is contained in a given set with absolute certainty. A mathematical expression which converts values to such possibilities is referred to as a membership function.
The references Ndouse, Bonde and U.S. Pat. No. 5,341,366 use fuzzy logic to control congestion or admission in a communications network. Ndouse uses fuzzy logic in the above-noted leaky bucket mechanism to adjust the thresholds at which selective discarding of cells occurs at a node to control the traffic load. Bonde also uses fuzzy logic to control the selective discarding of cells to adjust the traffic load at a node. Bonde uses fuzzy logic to determine the fraction of cells to discard based on the occupancy of the input cell queue of a node. U.S. Pat. No. 5,341,266 uses fuzzy logic to control the admission of new communications at a node. However, there is no general technique to design a fuzzy logic engine for the admission controller (or congestion controller). Moreover, it is hard for a fuzzy logic admission controller to adapt itself to a dynamic environment (e.g., changing traffic loads and patterns).
U.S. Pat. No. 5,442,624 (Bonomi) proposes a dynamic access control method for an ATM network. In the Bonomi technique, the rate at which each source can provide packets to each node is dynamically changed based on the level of congestion in the respective VCC that carries the data of the source. To that end, each node periodically transmits so called "scout" cells on each VCC. The scout cell propagates from node to node unless it is discarded as a result of congestion at a particular node. If and when the scout cell reaches the destination node, it is transmitted back on the return VCC to the node which issued it. If the scout cell is received at the node from which it originally issued, the node from which it originally issued determines that there is no congestion on the respective VCC and the rate at which the source provides cells to that node for communication on that VCC is increased. On the other hand, if the scout cell is not received at the node from which it originally issued, the node which originally issued the scout cell determines that the scout cell has been discarded as a result of congestion on the VCC and the node decreases the rate at which the source can produce cells for communication on that VCC. There are two problems with this technique. First, the scout cell may be discarded as a result of congestion on the return path rather than the forward path. This would cause a node to erroneously to reduce the cell transmission rate on the forward path. Second, considering that each node on the VCC periodically transmits scout cells, the scout cells themselves increase the load on the network and increase the likelihood of congestion.
The techniques described above utilize traffic parameters measured in the time domain to describe the characteristics of the incoming traffic for purposes of setting an admission control policy for adverting congestion. However, these parameters provide little information about the correlation of the traffic. As a result, the admission control policy is set based on incomplete information resulting in non-optimal utilization of bandwidth. San-Qu Li & Chia-Lin Hwang, Queue Response to Input Correlation Functions: Discrete Spectra Analysis, IEEE/ACM TRANS. ON NETWORKING, Vol. 1, No. 5, October 1994, pp. 522-533, San-Qu Li & Chia-Lin Hwang, Queue Response to Input Correlation Functions: Continuous Spectra Analysis, IEEE/ACM TRANS. ON NETWORKING, Vol. 1, No. 6, December 1993, pp. 678-691, and C. H. Lin, Traffic Control for an ATM Network Using Spectral Analysis, Master Thesis, Department of Communication Engineering, National Chiao Tung University (1994) have studied traffic parameters measured in the frequency domain to describe the characteristics of the incoming traffic. According to these references, multi-media traffic, in particular, the cell production rates of sources communicating voice or video information are considered to be highly correlated. For instance, a variable rate video signal produced according to MPEG will have a bit rate which depends upon whether intracoding or interceding is used wherein the bit rate is higher when intracoding is used as opposed to intercoding. Certain kinds of pictures, namely, I pictures, use only intracoding, whereas other kinds of pictures, such as P pictures and B pictures, may use either intracoding or intercoding (but tend to use little intracoding). Typically, the choice of whether or not each picture in a sequence of pictures is an I, P or B picture is predetermined according to a repeated sequence. For instance, every tenth picture in a sequence of pictures may be an I picture, every fourth and seventh picture may be a P picture, and every second, third, fifth, sixth eight and ninth picture may be a B picture.
According to these references, a typical multi-media traffic stream is modeled by a Markov modulated Poisson process (MMPP) as shown in FIG. 3. In such an MMPP model, the macro level correlation of the cell production rate of the source is modeled by a Markov chain wherein each state of the Markov chain is associated with a constant input rate. This reflects the macro level non-randomness of cell production, e.g., as in the case of encoded video, with a definite, I, P and B picture structure. On the other hand, in each state of the Markov chain, the arrival time of each individual cell is assumed to be random and is characterized by the Poisson distribution. Assume the cell production rate a(t) is an N+1 state MMPP represented as (Q, .gamma.) where Q is the state transition rate matrix and .gamma.=(.gamma..sub.0, .gamma..sub.1, . . . , .gamma..sub.N) is the vector representing the arrival rate at each MMPP state. Such a matrix Q and vector .gamma. can be easily generated from the
mean cell production rate R.sub.M, cell production peak rate R.sub.P and mean peak cell production rate duration T.sub.D, given the above assumptions for video (or similar reasoning for voice), using the following equations: ##EQU1## The steady state probably vector of Q is denoted by .pi.=(.pi..sub.0, .pi..sub.1, . . . , .pi..sub.N). .pi. can be solved by setting .pi.Q=0 and .pi.e=1 where e is a column vector with all elements equal to one. The average input rate .gamma. is then given by ##EQU2## Q is diagonalizable, and by spectral decomposition Q can be represented as ##EQU3## where .lambda..sub.1 is the 1.sup.th eigenvalue and g.sub.1 (h.sub.1) is the associated right column (left row) eigenvector of Q with respect to .lambda..
The auto-correlation function on an MMPP is defined as EQU R(.tau.)=a(t)a(t+.tau.)
and its corresponding power spectral density P(.omega.) can be obtained from: ##EQU4## where Im{.multidot.}, Re{.multidot.}, and arg{.multidot.} denote the imaginary part, the real part, and the phase of the argument, respectively. .psi..sub.0 is the DC component of the power spectral density P(.omega.) given by EQU .psi..sub.0 =.gamma..sup.2, (5)
and .psi..sub.1 is the average power contributed by .lambda..sub.1 and is given by ##EQU5## where g.sub.1i and h.sub.1j are i.sup.th and j.sup.th entities of the vector, respectively; b.sub.1 (.omega.) is the bell function with respect to .lambda..sub.1 and is given by ##EQU6## where B.sub.1 =-2Re{.lambda..sub.1 } is the half-power bandwidth and .omega..sub.1 =Im{.lambda..sub.1 } is the central frequency of the bell-shaped function b.sub.1 (.omega.).
From eq.(4), note that the power spectral density P(.omega.) is constituted by white nose .gamma., DC component 2.pi..psi..sub.0 .delta.(.omega.), and a set of bell-shaped functions b.sub.1 (.omega.). From eq.(8), note also that the bell-shaped function b.sub.1 (.omega.) is located at the central frequency .omega..sub.1 =Im{.lambda..sub.1 } and weighted by the average power .psi..sub.1. The shape of b.sub.1 (.omega.) is determined by the half-power bandwidth B.sub.1 =-2Re{.lambda..sub.1 }. The white noise is contributed by the Poisson local dynamics. If the source is MMDP (Markov Modulated Deterministic Process), it has no white noise component as it has no local dynamic in each state. From the studies in the Li and Hwang references, the results show that the influence of the white noise on a queuing system can be neglected.
The Lin reference has proposed to construct an admission control criterion using the above power spectrum modelling. Specifically, each node models a number of variable bit rate sources, based on an expected QoS requirement and likely received parameters R.sub.M, R.sub.P and T.sub.D using the above analysis, to produce the three power spectrum parameters (.gamma.,B,.PSI.) for each modelled source. (Only one half-power bandwidth B is produced since each source is presumed to have only a single bell function b.) The spectrum parameters are then used to construct a connection admission control table. The problem with this strategy is that such a CAC table is complex and has a very large dimension.
It is an object of the present invention to overcome the disadvantages of the prior art.